package com.example.leetcode.DynamicProgramming;

/**
 *
 *
 *  dp[0] = 0
 *  dp[1] = Math.max(dp[0], prices[1] - min(prices));
 *  dp[n] = Math.max(dp[n-1], prices[n] - minCost);
 *  思路解读：当前的价格减去前几天的最低价格，与前一天的最大利润进行比较
 *
 * @Description TODO
 * @date 2021/6/30 8:41
 * @Author liuzhihui
 * @Version 1.0
 */
public class Solution_4_121 {
    public static void main(String[] args) {
        int[] prices = new int[]{7,1,5,3,6,4};
//        int[] prices = new int[]{7,6,4,3,1};
        int i = maxProfit(prices);
        System.out.println(i);
    }
    public static int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];

        dp[0] = 0;

        int minCost = prices[0];

        for (int i = 1; i < prices.length; i++) {
            minCost = Math.min(minCost,prices[i]);
            dp[i] = Math.max(dp[i -1],prices[i] -minCost);

        }
        return dp[prices.length - 1];
    }
}
